package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/merge-k-sorted-lists/description/
 *
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * @author hanjuntao
 * @date 2025/8/15 0015
 */
public class L_23_合并K个升序链表 {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;

        ListNode node4 = new ListNode(2);
        ListNode node5 = new ListNode(5);
        node4.next = node5;

        ListNode[] lists = new ListNode[2];
        lists[0] = node1;
        lists[1] = node4;

        ListNode result = mergeKLists(lists);
        ListNode.print(result);
    }

    /**
     *
     * 该题可以退化为两个链表合并
     * 多次使用
     *
     *
     * @param lists
     * @return
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        for (int i = 0; i < lists.length - 1; i++) {
            lists[i + 1] = mergeTwoLists(lists[i], lists[i + 1]);
        }

        return lists[lists.length - 1];
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyNode = new ListNode(-1);

        ListNode cur1 = l1;
        ListNode cur2 = l2;

        ListNode cur = dummyNode;

        while (cur1 != null && cur2 != null) {
            // 谁小谁先走
            if (cur1.val < cur2.val) {
                // 放到新链表中
                cur.next = cur1;

                // 断链
                ListNode next = cur1.next;
                cur1.next = null;

                // 指向下一个
                cur1 = next;
                cur = cur.next;
            } else {
                // 放到新链表中
                cur.next = cur2;

                // 断链
                ListNode next = cur2.next;
                cur2.next = null;

                // 指向下一个
                cur2 = next;
                cur = cur.next;
            }
        }

        if (cur1 != null) {
            cur.next = cur1;
        }
        if (cur2 != null) {
            cur.next = cur2;
        }

        ListNode next = dummyNode.next;
        dummyNode.next = null;
        return next;
    }
}
